class Solution {
public:
    //创建K个数的大根堆；
    //将剩下的数和堆顶元素进行比较，如果小于堆顶元素，就把堆顶元素替换成该元素
    //依次向后比较，重复以上步骤
    //此时数组中前K个数即为最小的K个数
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=k;
        for(int i=len/2-1;i>=0;i--)
        {
            adjustMaxHeap(input,i,len);
        }
        for(int i=k;i<input.size();i++)
        {
            if(input[i]<input[0])
            {
                input[0]=input[i];
                adjustMaxHeap(input, 0, len);
            }
        }
        vector<int> ans;
        for(int i=0;i<k;i++)
        {
            ans.push_back(input[i]);
        }
        return ans;
    }
    void adjustMaxHeap(vector<int> &arr,int pos,int len)
    {
        int dad =pos;
        int son=2*dad+1;
        while(son<len)
        {
            if(son+1<len&&arr[son+1]>arr[son])
            {
                son++;
            }if(arr[son]>arr[dad])
            {
                swap(arr[son],arr[dad]);
                dad=son;
                son=2*dad+1;
            }
            else
                break;
        }
    }
};